--- categories: Graph theory --- *Dilworth's theorem* states that the length of a longest [antichain](Partially ordered set#Antichain) in a [partially ordered set](Partially ordered set) $S$ is equal to the size of a minimum [partition](Partition) of $S$ into [chains](Partially ordered set#chain). If the poset is represented as a [directed acyclic graph](Directed acyclic graph), the minimum partition into chains is equivalent to the [vertex-disjoint path cover](Vertex-disjoint path cover) problem. > **Note**: Posets are [transitive](Transitivity) by nature. If a poset is represented in compressed form as a DAG, then the [transitive closure](Transitive closure) must be taken before computing the vertex-disjoint path cover. ## Problems - [Fat Hobbits](http://acm.timus.ru/problem.aspx?space=1&num=1533) - [Nested Dolls](https://archive.algo.is/icpc/nwerc/ncpc/2007/ncpc2007problems.pdf) - [Incubator](https://community.topcoder.com/stat?c=problem_statement&pm=12080) [^1] - [Gentrification](http://codeforces.com/gym/100591) - [Birthday](http://codeforces.com/contest/590/problem/E) [^2] ## See also - [Vertex-disjoint path cover]() - [Hall's marriage theorem](Hall's marriage theorem) ## External links - [Dilworth's theorem](https://en.wikipedia.org/wiki/Dilworth%27s_theorem) - [Partially Ordered Sets](http://codeforces.com/blog/entry/3781) [^1]: [^2]: